﻿// 擂台游戏.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//


/*
https://www.acwing.com/file_system/file/content/whole/index/content/12655086/
https://www.luogu.com.cn/problem/P11234
 
小 S
 想要举办一场擂台游戏，如果共有 2k
 名选手参加，那么游戏分为 k
 轮进行：

第一轮编号为 1,2
 的选手进行一次对局，编号为 3,4
 的选手进行一次对局，以此类推，编号为 2k−1,2k
 的选手进行一次对局。
第二轮在只保留第一轮的胜者的前提下，相邻的两位依次进行一场对局。
以此类推，第 k−1
 轮在只保留第 k−2
 轮的 4
 位胜者的前提下，前两位、后两位分别进行对局，也就是所谓的半决赛。
第 k
 轮即为半决赛两位胜者的决赛。
确定了游戏晋级的规则后，小 S
 将比赛的规则设置为了擂台赛。

具体而言，每位选手都有一个能力值 a1,a2,⋅⋅⋅,a2k
，能力值为 [0,231−1]
 之内的整数。

对于每场比赛，会先抽签决定一个数 0/1
，我们将第 R
 轮的第 G
 场比赛抽到的数记为 dR,G
。

抽到 0
 则表示表示编号小的选手为擂主，抽到 1
 则表示编号大的选手为擂主。

擂主获胜当且仅当他的能力值 a≥R
。

也就是说，游戏的胜负只取决于擂主的能力值与当前比赛是第几轮的大小关系，与另一位的能力值无关。

现在，小 S
 先后陆续收到了 n
 位选手的报名信息，他们分别告知了小 S
 自己的能力值。

小 S
 会按照报名的先后顺序对选手进行编号为 1,2,⋅⋅⋅,n
。

小 S
 关心的是，补充尽量少的选手使总人数为 2
 的整次幂，且所有选手进行一次完整的擂台游戏后，所有可能成为总冠军的选手的编号之和为多少。

形式化地，设 k
 是最小的非负整数使得 2k≥n
，那么应当补充 (2k−n)
 名选手，且补充的选手的能力值可以任取 [0,231−1]
 之内的整数。

如果补充的选手有可能获胜，也应当计入答案中。

当然小 S
 觉得这个问题还是太简单了，所以他给了你 m
 个询问 c1,c2,⋅⋅⋅,cm
。

小 S
 希望你帮忙对于每个 ci
 求出，在只收到前 ci
 位选手的报名信息时，这个问题的答案是多少。

输入格式
本题的测试点包含有多组测试数据，但不同测试数据只是通过修改 a1,a2,⋅⋅⋅,an
 得到，其他内容均保持不变，请参考以下格式。

其中 ⊕
 代表异或运算符，amodb
 代表 a
 除以 b
 的余数。

输入的第一行包含两个正整数 n,m
，表示报名的选手数量和询问的数量。

输入的第二行包含 n
 个非负整数 a′1,a′2,⋅⋅⋅,a′n
，这列数将用来计算真正的能力值。

输入的第三行包含 m
 个正整数 c1,c2,⋅⋅⋅,cm
，表示询问。

设 K
 是使得 2K≥n
 的最小的非负整数，接下来的 K
 行当中，第 R
 行包含 2K−R
 个数（无空格），其中第 G
 个数表示第 R
 轮的第 G
 场比赛抽签得到的 dR,G=0/1
。

注意，由于询问只是将人数凑齐到 2k≥ci
，这里的 k≤K
，因此你未必会用到全部的输入值。

接下来一行包含一个正整数 T
，表示有 T
 组测试数据。

接下来共 T
 行，每行描述一组数据，包含 4
 个非负整数 X0,X1,X2,X3
，该组数据的能力值 ai=a′i⊕Ximod4
，其中 1≤i≤n
。

输出格式
共输出 T
 行，对于每组数据，设 Ai
 为第 i
（1≤i≤m
）组询问的答案，你只需要输出一行包含一个整数，表示 (1×A1)⊕(2×A2)⊕⋅⋅⋅⊕(m×Am)
 的结果。

数据范围
对于所有测试数据，保证：2≤n,m≤105
，0≤ai,Xj<231
，1≤ci≤n
，1≤T≤256
。

QQ截图20241106162910.png

特殊性质 A
：保证询问的 ci
 均为 2
 的幂次。
特殊性质 B
：保证所有的 dR,G=0
。

输入样例：
5 5
0 0 0 0 0
5 4 1 2 3
1001
10
1
4
2 1 0 0
1 2 1 0
0 2 3 1
2 2 0 1
输出样例：
5
19
7
1
样例解释
共有 T=4
 组数据，这里只解释第一组。

5
 名选手的真实能力值为 [1,0,0,2,1]
。

5
 组询问分别是对长度为 5,4,1,2,3
 的前缀进行的。

对于长度为 1
 的前缀，由于只有 1
 号一个人，因此答案为 1
。
对于长度为 2
 的前缀，由于 2
 个人已经是 2
 的幂次，因此不需要进行扩充。根据抽签 d1,1=1
 可知 2
 号为擂主，由于 a2<1
，因此 1
 号获胜，答案为 1
。
对于长度为 3
 的前缀，首先 1
 号、2
 号比赛是 1
 号获胜（因为 d1,1=1
，故 2
 号为擂主，a2<1
），然后虽然 4
 号能力值还不知道，但 3
 号、4
 号比赛一定是 4
 号获胜（因为 d1,2=0
，故 3
 号为擂主，a3<1
），而决赛 1
 号、4
 号谁获胜都有可能（因为 d2,1=1
，故 4
 号为擂主，如果 a4<2
 则 1
 号获胜，a4≥2
 则 4
 号获胜）。综上所述，答案为 1+4=5
。
对于长度为 4
 的前缀，我们根据上一条的分析得知，由于 a4≥2
，所以决赛获胜的是 4
 号。
对于长度为 5
 的前缀，可以证明，可能获胜的选手包括 4
 号、7
 号、8
 号，答案为 19
。
因此，该组测试数据的答案为 (1×19)⊕(2×4)⊕(3×1)⊕(4×1)⊕(5×5)=5
。
*/
#include <iostream>

int main()
{
    std::cout << "Hello World!\n";
}

 